COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002			    Concerning a Computability Course
C00012 ENDMK
C⊗;
		    Concerning a Computability Course

The thrust of  the "Computing and  Cultures" proposal was  an appeal to  a
broad base of lower division general  University students. As a result,  I
played down  the formal  aspects,  and stressed  the implications  of  the
technology and formalism. However, rigor  IS there: we would discuss  many
rather deep areas  including the relationships  between truth,  deduction,
and computation as illuminated in Godel's and Church's results.  I believe
that one cannot intelligently discuss the applications and implications of
a technical area without having an accurate picture of the potentials  and
limitations of that subject; so the preparation for the "deep results"  is
substantial --substantial,  but not  insurmountable.  Axiom  systems,  the
notions of truth, and a firm grasp of computational ideas can all be aided
substantially using  a computer-based  system. Substantial  work has  been
done at Stanford and other institutions,  to bring computation to bear  on
traditional disciplines. Though I worked with the Stanford people  several
years ago, my  approach is  quite different: do  not use  the computer  to
augment an existing  curriculum; rather rework  the curriculum around  the
machine. This  was  the thrust  of  EECS129,  and also  the  force  within
"Computing and Cultures": use the machine to induce thinking.

You expressed interest in a course on computability and its  implications;
this same  collection of  ideas, now  with an  emphasis on  the logic  and
computability issues could serve the purpose nicely.

Rather than  building on  Turing machines,  I favor  the lambda  calculus.
Besides being computationally  equivalent to Turing  machines, the  lambda
calculus offers several advantages:

1.  The computational model is much  more robust than that exhibited by  a
Turing machine.  One can attempt to understand mental activity in terms of
neural-level chemical and electrical activity; so too, one can attempt  to
understand the  functioning of  a  complex computer  program in  terms  of
chip-level electrical signals. The Turing model of computation has similar
problems of "level"  when used to  explicate complex computational  ideas.
The computational models for the lambda calculus are much more amenable to
complex reasoning.   One  can  easily develop  the  notions  of  universal
machines  and  questions  of  unsolvability,  and  discuss  incompleteness
results using lambda calculus-based models; and  it can be done with  much
less fuss and bother.

2.  It is the basis of much  of the theoretical work in computer  science.
Most of the work in  the mathematical theory of computation  --correctness
and equivalence of programs, semantics of programming languages, ...--  is
being done in formalisms based on the lambda calculus. In particular,  the
work deals with, and is implemented in, a programming language named LISP.
It is this language that  is the driving force in  all the courses I  have
taught and proposed at Santa Clara University.

3.  It is the  basis of some  of the most  exciting work in  applications.
Most of  the work  in  Artificial Intelligence  (AI)  is written  in  some
dialect of LISP. LISP has  been the mainstay of  AI for over twenty  years
and shows no  sign of diminishing  its hold.  Indeed,  since AI is  "going
commercial" there is  a substantial shortage  of  LISP programmers;  since
the field is lucrative as well as entertaining and challenging, one  could
do worse than learn LISP.

4.  Furthermore, many LISP-based educational projects are emerging: MIT is
revamping their undergraduate mathematics and physics curricula using LISP
notions.  My Santa Clara  proposal is a first  step in this direction  for
more general educational programs.

5.   There   is   a   rapidly  expanding   interest   in   lambda-calculus
architectures.  Several manufacturers of computers have projects  underway
to build  lambda  calculus  machines. These  are  not  special-purpose  AI
machines, but  general-purpose computing  devices. People  who  understand
this new kind of computing will be in demand.

Of course, the  point of these  courses is not  to train programmers;  the
point is  to teach  rigorous thinking.   This has  been and  still is  the
province of mathematics and philosophy programs; unfortunately, industries
--particularly in this valley-- have been placing a higher premium on  the
"instant gratification" of technological training, than on the ability  to
do sustained  thought.  Unfortunately,  few computer  science  departments
have been  able to  mount an  effective campaign  against this  short-term
job-oriented mentality   and  teach  fundamental  principles  rather  than
job-skills.  It is a bankrupt policy, already showing signs of failure  in
the loss of technological edge to  foreign competition. These are some  of
the reasons  that  I brought  my  "campaign"  to SCU:   computation  is  a
beautiful theoretical and  practical subject,  with a kernel  of ideas  as
worthwhile and enduring as  one will find in  any discipline. These  ideas
build on the lambda calculus; these  ideas form the kernel of the  courses
at Santa Clara.

In short, it is an incredibly rapid  way to bring people to the  forefront
of computing ideas, perhaps similar in its power and elegance to that  the
world experienced  in moving  from Roman  numerals to  the Arabic  system:
"difficult" notions become "easy".

Source materials are  scattered, but  substantial. There are  a couple  of
books that are partially adequate --one of which I will use this fall in a
graduate EECS course  called "Functional Programming";  there is Dr.  Ruth
Davis's Masters   thesis as  well as  a  series of  lecture notes  from  a
short-course given in England, and finally, I have a book underway.

I hope this  outline helps a  bit; if you  or your faculty  would like  to
discuss any of these issues, please feel  free to contact me.  There is  a
wide latitude in content and depth --from abstract recursion theory to  an
analysis of AI; I hope  we can come to an  agreement.  If a course can  be
established, I would suggest that it happen in Winter term, and draw  from
the  Junior  class.   Teaching  Seniors  in  the  Spring  can  be   pretty
depressing.